class Point {
    constructor(name) {
        // 识别节点
        this.name = name
        // 可达节点
        this.children = []
        // 最短路径
        this.path = []
    }
}

const p1 = new Point('1')
const p2 = new Point('2')
const p3 = new Point('3')
const p4 = new Point('4')
const p5 = new Point('5')

p1.children = [{node:p2,len:6}, {node:p4,len:2}]
p2.children = [{node:p1,len:6},{node:p3,len:3},{node:p4,len:3},{node:p5,len:7}]
p3.children = [{node:p4,len:1},{node:p5,len:2}]
p4.children = [{node:p1,len:2},{node:p2,len:3},{node:p5,len:9}]
p5.children = []

// 广度优先

function bfs(root) {
    const queue = new PriorityQueue({comparator: function(a, b){return a.totalLen-b.totalLen; }})
    const map = new Map()
    // 设置根节点
    map.set(root,0)
    queue.queue({node:root,totalLen:0})
    root.path = [root]
    // 遍历
    while (queue.length > 0) {
        const current = queue.dequeue()
         current.node.children.forEach(child => {
            const totalLen = current.totalLen + child.len
            if (!map.has(child.node) || map.get(child.node) > totalLen) {
                queue.queue({node:child.node,totalLen})
                map.set(child.node,totalLen)
                child.node.path = [...current.node.path, child.node]
            }
        })
    }
}
bfs(p1)


function bfss2(root){
    var queue=new PriorityQueue({comparator: function(a, b){return a.totalLen-b.totalLen; }});;
    var set = new Map();
    set.set(root, 0);
    queue.queue({node:root,totalLen:0});
    root.path = [root]
    while(queue.length>0){
        var cur = queue.dequeue();
        if(set.get(cur.node)<cur.totalLen)continue;
        cur.node.children.forEach(it=>{
            if(!set.has(it.node) || set.get(it.node) > cur.totalLen + it.len){
                queue.queue({node:it.node,totalLen: cur.totalLen + it.len});
                set.set(it.node,cur.totalLen + it.len)
                it.node.path = [...cur.node.path,it.node];
            }
        })
    }
}


// const matrix = [
//     [0,1,0,1,0],
//     [0,0,1,1,1],
//     [0,0,0,1,1],
//     [1,0,0,0,0],
//     [0,0,0,0,0]
// ]
// const path = [[],[],[],[],[]]
// function bfs2(root){
//     const queue = [root]
//     const set = new Set()
//     set.add(root)
//     path[root] = [root+1]
//     while(queue.length > 0){
//         const current = queue.pop()
//         for(let i = 0;i<matrix.length;i++){
//             if(matrix[current][i] && !set.has(i)){
//                 set.add(i)
//                 queue.unshift(i)
//                 path[i] = [...path[current],i+1]
//             }
//         }
//     }
// }
// bfs2(0)
// console.log(path)

const matrix = [
    [0,6,Infinity,2,Infinity],
    [6,0,3,3,7],
    [Infinity,Infinity,0,1,2],
    [2,3,Infinity,0,9],
    [Infinity,Infinity,Infinity,Infinity,0]
]
function dijkstra(root){
    const len = matrix.length
    const dis = new Array(len).fill(Infinity) // 前面的优先队列
    const set = new Array(len).fill(0) // 前面的 set
    const pathes = []
    dis[root] = 0
    pathes[root] = [root]

    for (let i = 0; i < len; i++) {
        let min = Infinity
        let minIndex = -1
        // 前面的优先队列
        for (let j = 0; j < len; j++) {
            if(set[j] === 0 && dis[j] < min){
                minIndex = j
                min = dis[j]
            }            
        }
        // 遍历过了
        set[minIndex] = 1

        for (let j = 0; j < len; j++) {
            if(matrix[minIndex][j] !== Infinity
                && matrix[minIndex][j] + dis[minIndex] < dis[j]){
                    dis[j] = matrix[minIndex][j] + dis[minIndex]
                    pathes[j] = [...pathes[minIndex],j];
            }
            
        }
    }
    console.log(pathes,dis)
}
dijkstra(0)